package com.example.hot100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 *
 *  示例 1：
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 *
 *  示例 2：
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 *
 *  示例 3：
 * 输入：s = ""
 * 输出：0
 */
public class Leetcode32_LongestValidParentheses {
    public static void main(String[] args) {
        String s = ")()())";
//        s = "(()";
//        s = "()";
        System.out.println(new Solution().longestValidParentheses(s));
    }

    static class Solution {
        /**
         * 解法三：动态规划
         * @param s
         * @return
         */
        private int longestValidParentheses3(String s) {
            if (s == null || s.length() <= 1) return 0;
            int maxSubLen = 0;
            int len = s.length();
            int[] dp = new int[len]; // dp[i] 表示以下标 i 字符结尾的最长有效括号的长度

            char[] chars = s.toCharArray();
            for (int i = 1; i < len; i++) {
                if (chars[i] == ')') {
                    if (chars[i - 1] == '(') { // ....() 这种形式要看以chars[i - 2]为结尾的最长有效括号的长度
                        dp[i] = i - 2 > 0 ? dp[i - 2] + 2 : 2;
                    } else if (chars[i - 1] == ')' && i - dp[i - 1] - 1 >= 0 && chars[i - dp[i - 1] - 1] == '(') {
                        // ....)) 这种形式
                        if (i - dp[i - 1] - 2 > 0) {
                            dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
                        } else {
                            dp[i] = dp[i - 1] + 2;
                        }
                    }

                    maxSubLen = Math.max(maxSubLen, dp[i]);
                }/* else { // 以'('为结尾的字符串必定不能可能组成有效括号(可以省略)
                    dp[i] = 0;
                }*/
            }

            return maxSubLen;
        }

        /**
         * 解法二:栈
         * @param s
         * @return
         */
        private int longestValidParentheses2(String s) {
            if (s == null || s.length() <= 1) return 0;
            int maxSubLen = 0;
            char[] chars = s.toCharArray();
            Deque<Integer> stack = new LinkedList<>(); // 栈底表示当前已经遍历过的元素中 最后一个没有被匹配的右括号的下标
            stack.push(-1); // 初始化栈
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == '(') stack.push(i); // 左括号时将对应的下标入栈
                else { // 右括号时，先将栈顶元素出栈
                    stack.pop();
                    if (stack.isEmpty()) // 如果栈空说明当前的右括号为没有被匹配的右括号，此时需要更新 最后一个没有被匹配的右括号的下标
                        stack.push(i);
                    else
                        maxSubLen = Math.max(maxSubLen, i - stack.peek());
                }
            }

            return maxSubLen;
        }

        /**
         * 暴力法:逐个子串进行判断是否是有效括号(超时)
         * @param s
         * @return
         */
        private int longestValidParentheses1(String s) {
            if (s == null || s.length() <= 1) return 0;
            int maxSubLen = 0;
            int len = s.length();
            for (int i = 0; i < len; i++) {
                for (int j = i + 1; j <= len; j++) {
                    int subLen = j - i;
                    if (subLen % 2 == 0 && subLen > maxSubLen && isValidParentheses(s.substring(i, j))) {
                        maxSubLen = Math.max(maxSubLen, subLen);
                    }
                }
            }
            return maxSubLen;
        }

        private boolean isValidParentheses(String str) {
            Deque<Character> stack = new LinkedList<>();
            int len = str.length();
            for (int i = 0; i < len; i++) {
                char ch = str.charAt(i);
                if (ch == ')') {
                    if (stack.isEmpty() || stack.peek() != '(') {
                        return false;
                    }
                    stack.pop();
                } else {
                    stack.push(ch);
                }

            }
            return stack.isEmpty();
        }

        public int longestValidParentheses(String s) {
            return longestValidParentheses3(s);
        }
    }
}
